package com.yiwenup.leetcode.offer;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
 * <p>
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 * <p>
 * 执行用时：64 ms, 在所有 Java 提交中击败了90.69%的用户
 * 内存消耗：52.3 MB, 在所有 Java 提交中击败了10.93%的用户
 **/
public class No041 {

    /**
     * 小顶堆，保存较大的一半
     */
    private Queue<Integer> minHeap = new PriorityQueue<>();

    /**
     * 大顶堆，保存较小的一半
     */
    private Queue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));

    /**
     * initialize your data structure here.
     */
    public No041() {

    }

    public void addNum(int num) {
        if (minHeap.size() != maxHeap.size()) {
            minHeap.add(num);
            maxHeap.add(minHeap.poll());
        } else {
            maxHeap.add(num);
            minHeap.add(maxHeap.poll());
        }
    }

    public double findMedian() {
        return minHeap.size() != maxHeap.size() ? minHeap.peek() : (minHeap.peek() + maxHeap.peek()) / 2.0;
    }

}
